1. Field of the Invention
The present invention is related to the resolution of collisions when hashing techniques are used to search and retrieve data from memory in a data processing system. More specifically, the invention is particularly useful for the resolution of page table collisions during the translation of a virtual address to a real address in a data processing system.
2. Description of the Background Art
Techniques which efficiently store, search and retrieve information are crucial for modern day data processing systems, particularly in large main frame systems. Hashing is commonly utilized to obtain information from records in a data base where each record is partitioned into a key portion and a data portion. The key portion is used to manage operations which utilize the record for retrieval, modification and maintenance functions. A description of existing techniques for hashing may be found in the survey and tutorial series of the IEEE publication Computer, October 1988, which is entitled "Hashing for Dynamic and Static Internal Tables" by Ted G. Lewis and Curtis R. Cook, pages 45-56.
The design of records which utilize key fields is described in the article entitled "A Simple Guide to Five Normal Forms in Relational Database Theory" by William Kent in the Communications of the ACM, February 1983, Vol. 26, No. 2, pp 120-125. This article provides insight into the selection of a key relative to the information that is contained in the record in order to provide for efficient update and to prevent data inconsistency.
As software systems become more and more complex, there is an increasing demand for more storage. Virtual storage systems are able to satisfy this demand in a manner which is transparent to the user who may regard all the storage space as addressable main storage due to the mapping of virtual addresses into real addresses. In such systems the size of the virtual storage is limited by the addressing scheme of the computer system and the amount of auxiliary storage available, and not by the number of main storage locations. The translation of virtual addresses into physical addresses that can be used to access memory is accomplished by dividing the virtual addressing space into fixed size segments referred to as "pages", which are analogous to the data portions of the records in a data base. The virtual address space is divided into pages, and page table entries are used to designate those pages which are currently resident in main, or real, memory. The classical method of accomplishing this is to select part of the virtual address as an index. Another portion of the virtual address is selected as a comparison segment. The remaining bits of the virtual address then serve as the in-page, or offset, address into the page. The combined index and comparison portions of the virtual address are analogous to the key portion of a record in a data base system.
In order to map a very large number of words of virtual space to real memory, a direct page table would be infeasibly large. (For example, 2.sup.54 words of virtual space, using 2.sup.12 word pages, would have to have 2.sup.42 entries, regardless of real memory size.) An approach taken in the past has been to have a page table entry only for those pages which are resident in real memory, which limits the number of page table entries to a reasonable number. The problem is still presented as to how to access the page table entries for a given virtual address. This has been accomplished by allowing a number of least significant bits (for example, 12) to be used as the offset into the page and to use the next N significant bits to index into the page table. When used in this fashion, the operation is referred to as "hashing", and the page table is also termed a hash table. The entries into the hash table initiate a number of chains of page table entries all of which have the same value of N bits. Each of the entries contains the remaining bits of the virtual address that it represents, and the value of N is determined by the hardware and software that is utilized to implement the algorithm.
In operation of this system, the instruction processor goes to the hash entry that is specified by these N bits and locates a chain of all pages whose virtual addresses include the same value of the N bits. The instruction processor then progresses through the chain from one page entry to the next, and at each entry compares the comparison portion of the virtual address to be located with a stored comparison portion of the page table entry until a match is obtained. Once a match is obtained, the real page address is retrieved from the entry, and then concatenated with the page offset to form the complete real address. In the event that the instruction processor does not find a match in the chain, (i.e., there is is no entry containing the value of the comparison portion), the page is not resident in real memory. Paging translation methods of the prior art that utilize the above-described chaining techniques are slow and have a detrimental impact on the performance of the system. In addition, there may be undesirable variations in system performance depending on the length of the chains.
The more detailed description of the prior art techniques with reference to FIG. 1 which follows is included with the intention of more distinctly defining the present invention over such prior art techniques. Paging techniques have been utilized to access memory in virtual memory systems through the use of key fields. For example, referring to FIG. 1, in such systems virtual address requests 10, 12 may be used to map large virtual addresses into comparatively small real address space. This is accomplished by dividing the virtual addresses into compare, index (or key), and offset segments. The index, or key, portions 14, 16 of the virtual addresses 10, 12 are used to reference memory locations in a page table 32. The compare portions 18, 20 of the virtual addresses 10, 12 represent values, each of which may be associated with a number of page table entries. The page offsets 22, 24 of the virtual addresses 10, 12 represent the offset location of the requested address in a page, which may be utilized along with an appropriate real page address 36 to obtain a real address 28. Since only the index portions 14, 16 of the virtual addresses 10, 12 are utilized to select page table entry 34, auxiliary techniques must be employed to resolve conflicts among non-unique index portions in a paged virtual memory system of the described type. One such technique previously mentioned is the chaining method.
When prior art virtual memory systems incorporate tables, such as the page table 32, the value of the index 14 of the virtual address 10 is used to locate the desired page table entry 34 in the page table 32. The page table entry 32 includes a specified real page address 36 and a compare segment 38. A second virtual address 12 can also be used to locate a second entry in the same page table 32, wherein its index value 16 may be the same as index value 14, providing there is no conflict between the values of the compare segments 18 and 20. FIG. 1 illustrates a prior art implementation in which index 14 and index 16 both point to the same page table entry 34. Because of this possibility of encountering non-unique index values, it is necessary to look at the compare portion 38 of the page table entry 34, and to compare this with the compare portions 18, 20 of the virtual addresses 10 and 12, respectively. Although FIG. 1 implies that this comparison takes place in a simultaneous manner, sequential comparison of the compare segment 18 with the compare segment 38, either followed, or preceded, by comparison of the compare segment 20 with the compare segment 38, is consistent with prior art implementations. This comparison may be achieved by use of either a hardware comparator, or through a software algorithm, either of which may be achieved in various ways now known to those skilled in the art. It is assumed in this description that a comparison match occurs between the compare segment 18 and compare segment 38, but that no match occurs between the compare segment 20 and the compare segment 38.
The values of compare segment 18 of virtual address 10 and of the compare segment 38 of the page table entry 34 are coupled to a comparison device, or step, 40, as represented by the line 42 and the lines 43, 44. In a hardware implementation, these lines each represent signal-carrying data lines. In a software implementation, they represent program data flow. The comparison check provided by the comparison device or step 40 thus indicates a match on the lines 46, 48, which are coupled to enable the enabling gates, or steps, 50, 52, respectively, which may be achieved through either hardware or software implementation.
If the compare segments 18 and 38 are equal, the enabling gate 50 couples the offset segment 22 of the virtual address 10, as indicated by the lines 49 and 51, to serve as the least significant bits, or offset 26 of the real address 28. Likewise, the real page address 36 of the page table entry 34 is coupled, as represented by the lines 54 and 56 through the gate 52, to serve as the most significant bits portion 30 of the real address 28. The real page address 30 is combined with the offset portion 26 to form the total real address 28.
The comparison device, or step, 58, as the case may be according to whether implementation is accomplished through hardware or software, represents a comparison of the compare segment 20 of the virtual address 12, with the compare segment 38 of the page table entry 34. The values of the compare segment 20 and of the compare segment 38 are coupled to the comparison device, or step, 58 for such comparison as represented by the line 60 and the lines 43, 45. The lines 60, 43, 45, like the lines 42, 43, 45, may represent either data lines or program data flow according to whether a hardware or software implementation is undertaken. In the illustrated embodiment, it is assumed that although index 14 and index 16 are equal, the values in compare segments 18 and 20 are not. Since the page table can contain only one page table entry which has a given index value, the page table entry 34 corresponds only to virtual address 10 and not to virtual address 12. This being the case, the comparison device, or step, 58 will indicate that there is no comparison for virtual address 12, and, as indicated by the output on the line 64 to the mass memory access 66, it will then be necessary to obtain the contents of virtual address 12 from mass storage since it will not be resident in the main memory. The complete virtual address 12 is supplied, as indicated by the line 68, to active mass memory access 66 so that it may be used to supply, as indicated by the line 70, data stored at the desired location in backup storage, since in the illustrated embodiment it is assumed that the compare segment 20 does not match the compare segment 38.
In other words, FIG. 1 does not illustrate the conflict case where both virtual addresses 10, 12 are present in main memory. If both of the virtual addresses are present in main memory, a conflict mechanism must be called to resolve the ambiguity. As previously noted, this is typically accomplished by searching an extended chain of page table entries, each of which point to another element in the chain, until the search terminates either by locating the desired real address, or by providing a "page fault" that indicates that the virtual address is not resident in main memory. The present invention is directed to an alternate conflict resolution mechanism which can determine page faults and resolve paging conflicts in a more efficient manner by guiding the search to a predictable number of memory references without penalizing non-conflict cases.